package com.github.hgkmail.hello.leetcode101.pointer.tree;

import com.github.hgkmail.hello.leetcode101.base.CommonUtil;
import com.github.hgkmail.hello.leetcode101.base.TreeNode;

import java.util.ArrayList;
import java.util.List;

//二叉树直径（diameter）：两侧高度和，即左子树高度 + 右子树高度
//二叉树最大直径：用递归遍历所有节点（本质是DFS，用的call stack）
//空节点，高度为0；非空节点，高度为1。
public class LC543DiameterOfBinaryTree {
    //遍历树，返回高度
    public int dfs(TreeNode node, List<Integer> diameter) {
        //end case
        if (node==null) {
            return 0; //空节点，高度为0
        }
        //divide
        int left=dfs(node.left, diameter);
        int right=dfs(node.right, diameter);
        //conquer
        int d = Math.max(diameter.get(0), left+right);
        diameter.set(0, d);
        return 1 + Math.max(left, right); //非空节点，高度为1，再加上子树高度
    }
    public int diameterOfBinaryTree(TreeNode root) {
        List<Integer> diameter = new ArrayList<>();
        diameter.add(0);

        dfs(root, diameter);

        return diameter.get(0);
    }

    public static void main(String[] args) {
        TreeNode a=new TreeNode(4, null, null);
//        TreeNode b=new TreeNode(5, null, null);
        TreeNode c=new TreeNode(2, a, null);
        TreeNode d=new TreeNode(3, null, null);
        TreeNode e=new TreeNode(1, c, d);
        System.out.println(new LC543DiameterOfBinaryTree().diameterOfBinaryTree(e));
        CommonUtil.printBinaryTree(e);
    }
}
